|A|=3, Äquivalenzrelationen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:55 Di 08.07.2014 | | Autor: | YuSul |
| Aufgabe | | Wie viele Äquivalenzrelationen gibt es auf der Menge [mm] $A=\{0,1,2\}$ [/mm] |
Hi,
ich habe eine Frage zu dieser Aufgabe. Und zwar verstehe ich nicht so wirklich wie es gemeint ist. Ich kann für die drei Elemente ja beliebig viele mögliche Relationen finden.
Zum Beispiel [mm] $x\sim [/mm] y$ genau dann wenn [mm] $x+y\in\mathbb{N}$ [/mm] oder
[mm] $x\sim [/mm] y$ genau dann wenn [mm] $x\cdot y\in\mathbb{N}$ [/mm] oder
[mm] $x\sim [/mm] y$ genau dann wenn $|x+y|<10$
[mm] $x\sim [/mm] y$ genau dann wenn $|x+y|<11$
usw.
Oder wie ist es gemeint? Auf obige weise kann ich ja unendlich viele Äquivalenzrelationen finden...
|
|
| |
|
Hallo,
> Wie viele Äquivalenzrelationen gibt es auf der Menge
> [mm]A=\{0,1,2\}[/mm]
> Hi,
>
> ich habe eine Frage zu dieser Aufgabe. Und zwar verstehe
> ich nicht so wirklich wie es gemeint ist. Ich kann für die
> drei Elemente ja beliebig viele mögliche Relationen
> finden.
>
> Zum Beispiel [mm]x\sim y[/mm] genau dann wenn [mm]x+y\in\mathbb{N}[/mm] oder
> [mm]x\sim y[/mm] genau dann wenn [mm]x\cdot y\in\mathbb{N}[/mm] oder
> [mm]x\sim y[/mm] genau dann wenn [mm]|x+y|<10[/mm]
> [mm]x\sim y[/mm] genau dann wenn [mm]|x+y|<11[/mm]
Keines davon ist eine Äquivalenzrelation auf A. Eine Relation auf A ist per Definition eine Teilemnge von $A [mm] \times [/mm] A$
> usw.
>
> Oder wie ist es gemeint? Auf obige weise kann ich ja
> unendlich viele Äquivalenzrelationen finden...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:14 Di 08.07.2014 | | Autor: | YuSul |
Und warum nicht?
Wenn ich das erste Beispiel nehme
[mm] $x\sim [/mm] y$ genau dann wenn [mm] $x+y\in\mathbb{N}$
[/mm]
Das ist klar, weil die natürlichen Zahlen bezüglich der Addition abgeschlossen sind und die Menge A nur natürliche Zahlen enthält.
(x,x) ist eine Element der Relation, da [mm] $x+x\in\mathbb{N}$
[/mm]
Symmetrie ist wegen
[mm] $(x,y)\in\sim$, [/mm] also [mm] $x+y\in\mathbb{N}\Rightarrow y+x\in\mathbb{N}\Rightarrow (y,x)\in\sim$
[/mm]
und Transitivität gilt auch...
[mm] $(x,y)\in\sim$ [/mm] und [mm] $(y,z)\in\sim$ [/mm] also
[mm] $x+y\in\sim$ [/mm] und [mm] $(y,z)\in\sim$, [/mm] dann ist auch [mm] $x+y\in\mathbb{N}\Rightarrow (x,z)\in\sim$
[/mm]
|
|
|
| |
|
> Und warum nicht?
> Wenn ich das erste Beispiel nehme
>
> [mm]x\sim y[/mm] genau dann wenn [mm]x+y\in\mathbb{N}[/mm]
>
> Das ist klar, weil die natürlichen Zahlen bezüglich der
> Addition abgeschlossen sind und die Menge A nur natürliche
> Zahlen enthält.
>
> (x,x) ist eine Element der Relation, da [mm]x+x\in\mathbb{N}[/mm]
>
> Symmetrie ist wegen
>
> [mm](x,y)\in\sim[/mm], also [mm]x+y\in\mathbb{N}\Rightarrow y+x\in\mathbb{N}\Rightarrow (y,x)\in\sim[/mm]
Damit diese Elementbeziehungen gelten können muss $ [mm] \sim [/mm] $ ja eine menge sein. Wie sieht diese aus?
> und Transitivität gilt auch...
>
> [mm](x,y)\in\sim[/mm] und [mm](y,z)\in\sim[/mm] also
>
> [mm]x+y\in\sim[/mm] und [mm](y,z)\in\sim[/mm], dann ist auch
> [mm]x+y\in\mathbb{N}\Rightarrow (x,z)\in\sim[/mm]
Du scheinst hier auch nur eine informelle Definition des begriffs relation zu verwenden, schau dir doch nochmal die formale Definition an, z.B. hier:
https://de.wikipedia.org/wiki/%C3%84quivalenzrelation
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:23 Di 08.07.2014 | | Autor: | YuSul |
Wir haben Äquivalenzrelation so definiert:
Eine (zweistellige) Relation R auf A heißt Äquivalenzrelation genau dann wenn
[mm] $(x,x)\in [/mm] R$
[mm] $(x,y)\in R\Rightarrow (y,x)\in [/mm] R$
[mm] $(x,y)\in [/mm] R und [mm] (y,z)\in R\Rightarrow (x,z)\in [/mm] R$
|
|
|
| |
|
Und wie habt ihr zwei-stellige relation definiert?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:25 Di 08.07.2014 | | Autor: | YuSul |
Ein [mm] $R\subset A\times A=\{(x,y): x\in A \wedge y\in A\}$ [/mm] heißt (zweistellige) Relation auf A.
|
|
|
| |
|
Das ist genau das was ich in der ersten Antwort geschrieben hab.
Meine sämtlichen Einwände bleiben also bestehen.
Was ist denn jetzt jeweils [mm] $\sim$ [/mm] ?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:34 Di 08.07.2014 | | Autor: | YuSul |
Auch wenn ich nur eine Teilmenge von A betrachte. Das ändert doch nichts daran, dass natürliche Zahlen addiert immer natürliche Zahlen bleiben.
Man hätte nur zu wenig Elemente....
|
|
|
| |
|
Hallo,
Du hast die Menge [mm] A:=\{1,2,3\}, [/mm] und Du sagst, daß die durch
a) [$ [mm] x\sim [/mm] y $] genau dann wenn [$ [mm] x+y\in\mathbb{N} [/mm] $] oder
b)[$ [mm] x\sim [/mm] y $] genau dann wenn [$ [mm] x\cdot y\in\mathbb{N} [/mm] $] oder
c)[$ [mm] x\sim [/mm] y $] genau dann wenn [$ |x+y|<10 $]
d)[$ [mm] x\sim [/mm] y $] genau dann wenn [$ |x+y|<11 $]
gegebenen Relationen [mm] R_1, R_2, R_3, R_4 [/mm] auf A Äquivalenzrelationen sind.
Ich stimme Dir zu.
Schauen wir uns die 4 Relationen mal an.
[mm] R_1=\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}=A\times [/mm] A
reflexiv, symmetrisch, transitiv ,
alles okay, Äquivalenzrelation.
[mm] R_2=\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}=A\times [/mm] A
reflexiv, symmetrisch, transitiv ,
alles okay, Äquivalenzrelation.
[mm] R_3=\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}=A\times [/mm] A
reflexiv, symmetrisch, transitiv ,
alles okay, Äquivalenzrelation.
[mm] R_4=\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}=A\times [/mm] A
reflexiv, symmetrisch, transitiv ,
alles okay, Äquivalenzrelation.
Inzwischen hast Du es gemerkt:
die von Dir angegebenen Relationen sind allesamt gleich, halt die komplette Menge [mm] A\times [/mm] A.
[mm] A\times [/mm] A ist eine 9-elementige Menge, und die Frage ist nun: welche ihrer weiteren Teilmengen sind auch Äquivalenzrelationen?
Das ist die Frage, welche hier im Raum steht.
LG Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:02 Di 08.07.2014 | | Autor: | YuSul |
Machen Relationen auf einelementige Mengen denn überhaupt Sinn?
Dann würde ich sagen, dass alle ihrer Teilmengen, außer die leere Menge Äquivalenzrelationen sind, bzw. man welche auf ihnen definieren kann.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:20 Di 08.07.2014 | | Autor: | hippias |
Du hast recht: Deine Beispiele sind allesamt Aequivalenzrelationen, und meiner Meinung nach hast Du sie auch voellig ueblich dargestellt. Worauf MaslanyFanclub und angela Dich aufmerksam machen wollten bzw. aufmerksam gemacht haben, ist, dass sie eben letztendlich alle gleich sind.
Es gibt also sicherlich unendlich viele Zeichenreihen, die z.B. im Deutschen eine Aequivalenzrelation auf $A$ definieren, aber die Aequivalenzrelationen selber, welche ja nach Definition Teilmengen von [mm] $A\times [/mm] A$ sind, koennen nicht alle verschieden sein.
Herausgefunden haben wir bisher, dass z.B. [mm] $\sim= A\times [/mm] A$ (alle Elemente sind zueinander aequivalent) eine solche ist. Naechstes Beispiel: [mm] $\{(1,1),(2,2), (3,3)\}$ [/mm] (jedes Element ist nur zu sich selber aequivalent; d.i. die Gleichheitsrelation). Hingegen ist [mm] $\{(1,2), (2,3), (3,1)\}$ [/mm] aus verschiedenen Gruenden keine Aequivalenzrelation auf $A$.
Verfolge Angelas Hinweis: welche Teilmengen von [mm] $A\times [/mm] A$ sind Aequivalenzrelationen? Ihr habt bestimmt einmal einen Zusammenhang zwischen Partitionen und Aequivalenzrelationen besprochen. Das koennte dir helfen.
> Machen Relationen auf einelementige Mengen denn überhaupt
> Sinn?
Ich habe keine Ahnung, was das mit Deiner Aufgabenstellung zu tun hat, aber Relationen auf einelementigen Mengen sind in der Tat nicht sehr spannend.
> Dann würde ich sagen, dass alle ihrer Teilmengen, außer
> die leere Menge Äquivalenzrelationen sind, bzw. man welche
> auf ihnen definieren kann.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:28 Di 08.07.2014 | | Autor: | YuSul |
Kann man diese Aufgabe also kombinatorisch lösen?
Nein, einen Zusammenhang zwischen Partitionen und Äquivalenzrelationen haben wir nicht besprochen, da wir den Begriff der Partition gar nicht eingeführt haben.
|
|
|
| |
|
Hallo,
mit Kombinatorik allein wird's nicht gehen.
Hast Du denn schon begonnen, die Teilmengen von [mm] A\times [/mm] A irgendwie systematisch zu untersuchen?
Wenn nicht, solltest Du einfach mal irgendwie starten.
Du könntest z.B. aus [mm] A\times [/mm] A ein Element herausnehmen und gucken, welche Konsequenzen das hat.
[Ansonsten würde es sich sicher lohnen, nochmal nachzulesen, ob "Partition" in dem Zusammenhang wirklich noch nicht dran war - könnte ja auch sein, daß es nur an Dir vorbeigerauscht ist.]
LG Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:12 Di 08.07.2014 | | Autor: | YuSul |
Nein, ist nicht an mir vorbei gerauscht.
Naja, im Grunde spielt es doch keine Rolle welche Elemente ich entferne. Da ja alle Elemente der Menge die selbe "Eigenschaft" haben und ich daher immer auf obige Weise auf jede Teilmenge eine Äquivalenzrelation definieren kann.
Es sollte dann doch [mm] |\mathcal{P}(A)|-1=7 [/mm] solcher Relationen geben. Die -1 weil die leere Menge raus genommen werden muss.
Nun müsste ich nur noch gucken ob da nicht noch welche Fehlen, weil ich ja auch das Kreuzprodukt beachten muss, welches Insgesamt 6 verschiedene Möglichkeiten liefert. Also
7+6=13 verschiedene solcher Relationen?
|
|
|
| |
|
> Naja, im Grunde spielt es doch keine Rolle welche Elemente
> ich entferne. Da ja alle Elemente der Menge die selbe
> "Eigenschaft" haben und ich daher immer auf obige Weise auf
> jede Teilmenge eine Äquivalenzrelation definieren kann.
>
> Es sollte dann doch [mm]|\mathcal{P}(A)|-1=7[/mm] solcher Relationen
> geben. Die -1 weil die leere Menge raus genommen werden
> muss.
> Nun müsste ich nur noch gucken ob da nicht noch welche
> Fehlen, weil ich ja auch das Kreuzprodukt beachten muss,
> welches Insgesamt 6 verschiedene Möglichkeiten liefert.
> Also
>
> 7+6=13 verschiedene solcher Relationen?
Hallo,
ich kann Deinen Ausführungen überhaupt nicht folgen - was aber nicht an Dir liegen muß.
Meine Anzahl ist nicht weit von Deiner entfernt.
Vielleicht zählst Du einfach mal Deine Äquivalenzrelationen auf, dann können wir ja gucken, ob Deine Überlegungen zum richtigen Ergebnis geführt haben.
LG Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:40 Di 08.07.2014 | | Autor: | YuSul |
Naja, aufgeschrieben habe ich bisher noch gar nichts, ich habe versucht es mir so zu überlegen...
Also die Potenzmenge von A enthält ja 8 Elemente. Sieben ohne der leeren Menge. Ich kann also
[mm] $\{0\}\times \{0\}$
[/mm]
[mm] $\{1\}\times \{1\}$
[/mm]
[mm] $\{2\}\times \{2\}$
[/mm]
Nun die zweielementigen Mengen:
[mm] $\{0,1\}\times \{0,1\}$
[/mm]
[mm] $\{0,2\}\times \{0,2\}$
[/mm]
[mm] $\{1,2\}\times \{1,2\}$
[/mm]
Und die Menge selbst
[mm] $\{0,1,2\}\times \{0,1,2\}$
[/mm]
Das wären die Möglichkeiten die man für die Teilmengen der normalen Menge hat. Wenn man nun die Teilmengen betrachtet, hmm, dann kann man doch einfach die Potenzmengen addieren, also
[mm] |\mathcal{P}(A)|+3|\mathcal{P}(B)|+3|\mathcal{P}(C)|-7
[/mm]
Womit ich auch noch alle möglichen Relationen der zwei elementigen (B) Mengen, und der 1 elementigen (C) Mengen betrachten würde.
Die -7 diesmal daher, da ich 7 mal die leere Menge mitzählen würde.
So käme ich auf
8+12+6-7=19
Wie viele Relationen würdest du denn erhalten?
Edit:
Moment, bei obiger Rechnung sollten sich welche doppeln.
|
|
|
| |
|
> Naja, aufgeschrieben habe ich bisher noch gar nichts, ich
> habe versucht es mir so zu überlegen...
Hallo,
bei Deinen ganzen Überlegungen fehlt mir der Aspekt, daß es sich um Äquivalenzrelationen handeln soll.
Ist das in Deinen Überlegungen berücksichtigt?
>
> Also die Potenzmenge von A enthält ja 8 Elemente. Sieben
> ohne der leeren Menge. Ich kann also
>
> [mm]\{0\}\times \{0\}[/mm]
> [mm]\{1\}\times \{1\}[/mm]
> [mm]\{2\}\times \{2\}[/mm]
>
> Nun die zweielementigen Mengen:
>
> [mm]\{0,1\}\times \{0,1\}[/mm]
> [mm]\{0,2\}\times \{0,2\}[/mm]
> [mm]\{1,2\}\times \{1,2\}[/mm]
>
> Und die Menge selbst
>
> [mm]\{0,1,2\}\times \{0,1,2\}[/mm]
Daß das Äquivalenzrelationen sind, hast Du geprüft?
>
> Das wären die Möglichkeiten die man für die Teilmengen
> der normalen Menge hat. Wenn man nun die Teilmengen
> betrachtet, hmm, dann kann man doch einfach die
> Potenzmengen addieren,
Jetzt hast Du mich abgehängt.
Ich weiß nicht, wovon Du sprichst.
> also
>
> [mm]|\mathcal{P}(A)|+3|\mathcal{P}(B)|+3|\mathcal{P}(C)|-7[/mm]
>
> Womit ich auch noch alle möglichen Relationen der zwei
> elementigen (B) Mengen, und der 1 elementigen (C) Mengen
> betrachten würde.
Wir wollen aber doch nicht alle möglichen Relationen betrachten, sondern alle möglichen Äquivalenzrelationen auf A herausfinden, dh. alle Teilmengen der 9-elementigen Menge [mm] A\times [/mm] A, welche Äquivalenzrelationen sind.
LG Angela
> Die -7 diesmal daher, da ich 7 mal die leere Menge
> mitzählen würde.
> So käme ich auf
>
> 8+12+6-7=19
>
> Wie viele Relationen würdest du denn erhalten?
>
> Edit:
>
> Moment, bei obiger Rechnung sollten sich welche doppeln.
|
|
|
| |
|
Eine alternative Beschreibung von Äquivalenzrelationen führt vielleicht schneller zum Ziel.
Demnach bilden die Äquivalenzklassen einer Äquivalenzrelation auf [mm]X[/mm] eine Zerlegung von [mm]X[/mm], d.h. [mm]X[/mm] ist die disjunkte Vereinigung der Äquivalenzklassen. Umgekehrt kann man eine beliebige Zerlegung von [mm]X[/mm] in nichtleere Teilmengen nehmen, und indem man zwei Elemente genau dann als äquivalent definiert, wenn sie derselben Zerlegungsmenge angehören, erhält man eine Äquivalenzrelation.
Nehmen wir unser [mm]A = \{ 1,2,3 \}[/mm]. Eine mögliche Zerlegung von [mm]A[/mm] wäre
[mm]A = \{ 1 \} \cup \{ 2,3 \}[/mm]
Und die beiden Glieder der Zerlegung sind jetzt genau die Äquivalenzklassen einer Äquivalenzrelation [mm]R[/mm], nämlich
[mm]1 \sim 1 \, ; \ \ \ 2 \sim 2 \, , \ 3 \sim 3 \, , \ 2 \sim 3 \, , \ 3 \sim 2[/mm]
In der Schreibweise als Teilmenge des kartesischen Produkts [mm]A \times A[/mm] sieht das so aus:
[mm]R = \left\{ (1,1), (2,2), (3,3), (2,3), (3,2) \right\}[/mm]
Jetzt muß man sich also nur die möglichen Zerlegungen von [mm]A[/mm] anschauen. Allzu viele sind das ja nicht.
|
|
|
|
